package com.jiang.daily.Q45;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/27 22:24
 */
class Solution {
    // 贪心（从后向前）
    public int jump(int[] nums) {
        int position = nums.length - 1; // 需要到的位置
        int step = 0;
        while(position > 0) {
            for (int i = 0; i < position; i++) {
                // 如果能到position
                if (i + nums[i] >= position) {
                    step++;
                    position = i;
                    break;
                }
                // 如果走完了还不能到position,则无法跳到最后位置（虽然题目要求是一定可以跳到最后位置，但这里依然可以返回无法跳到最后位置）
                if (i == position - 1) return -1;
            }
        }
        return step;
    }

    // 贪心（从前向后）
    // public int jump(int[] nums) {
    //     int len = nums.length;
    //     if (len == 1) return 0;
    //     int step = 0; // 跳跃次数
    //     int righMax = 0; // 最远跳的位置
    //     int end = 0; // 跳这一步的最远下标
    //     for (int i = 0; i < len; i++) {
    //         // 下一步的最远下标
    //         righMax = Math.max(righMax, i + nums[i]);
    //         // 如果下一步的最远下标大于等于最后位置，则返回step + 1
    //         if (righMax >= len - 1) return step + 1;
    //         // 如果这一步到了最远下标，开始新的一步
    //         if (i == end) {
    //             end = righMax;
    //             step++;
    //         }
    //     }
    //     // 虽然题目要求是一定可以跳到最后位置，但这里依然可以返回无法跳到最后位置
    //     return -1;
    // }
}
